This broadly relates to a method for numerical representation that can be advantageously applied to a method for compression and decompression of digital data, while allowing a minimization of selectable degree of the data amount and while maintaining their integrity.
It is known that one of the main problems in the computer technology and, more broadly, in the telecommunication technology, lies in the even increasing amount of data to be processed.
This entails a heavy exploitation of computer readable memories, such as removable (for instance CD-ROMS and floppy disks) or fixed (so-called computer Hard Disks) memory medium as well as an extended occupation of the telecommunication networks during information transmission, which, in turn, entails a higher transmission error probability, a higher transmission cost and a physical limitation to the feasibility of real time specific applications. In this regard, some applications can be mentioned in which transmission channels with limited capability are required for transmission of a noticeable amount of data; in detail, mention can be made of the attempt to realise an interactive television system, known as Video-on-Demand, based upon a twin wire telephone network that, due to intrinsic relevant channel limitations, is necessarily bound to transmit a lower data amount, thereby jeopardising the television image resolution.
The present numeric representation of digital data, namely the binary representation, is believed to be the most efficient and reliable.
When it is considered that the amount of information pieces stored in computers and/or exchanged through telecommunication networks is at present rapidly increasing, also due to the strong thrust exerted by the Internet Informatic Network extensively utilising information comprising large data amounts (such as the digital images), the problem of reducing the amount of data representing both information and application programs appears to be extremely critic.
Many approaches have been developed to solve the above mentioned problem, providing for encoding data represented in binary format, according to suitable methods, is in order to reduce the memory occupancy. Such encoding methods are usually particularly advantageous when they are applied to specific data types to be encoded, with specific characteristics. In other words, each individual encoding method turns out to be more or less advantageous according to whether it is applied for instance to data representing stationary images or to data representing video images or to data representing sounds.
The encoding methods can be classified based upon congruence between decoded data and original data or based upon fixed or variable length representation of original data and encoded data.
The first classification type divides the concerned encoding methods into methods having no information loss or xe2x80x9closslessxe2x80x9d methods, in which the data reconstructed or decoded from the encoded data are identical to the original ones, and methods having information losses or xe2x80x9clossyxe2x80x9d methods, in which the reconstructed data lose a portion of the original data information. Examples of lossless methods are the Run Length Encoding (RLE), the Huffman encoding method and the Lempel-Ziv-Welch or LZW encoding method; an example of lossy method is the Coarser Sampling and/or Quantization or CSandQ method.
According to the second classification type, the RLE and LZW encoding methods entail variable length original data and fixed length encoded data, the Huffman encoding method entails fixed length original data and variable length encoded data, the CSandQ encoding method entails both original data and encoded data with fixed length.
However, just because each encoding method is designed in connection with a specific type of data to be encoded, newer and newer encoding requirements for data having particular characteristics are being encountered.
Furthermore, the search of improved encoding methods aimed at even more compressing the data to be stored and/or transmitted is being even more developed.
The approach according to various embodiments of the present invention is to be considered in this context.
It is an object of this invention, therefore, to provide a method for numeric representation that is valid for any kind of data, is available to a xe2x80x9closslessxe2x80x9d compression and decompression method for digital data, while it enables the data amount to be selectively minimized.
It is specific subject matter of this invention a compression method for compressing an input data binary string, having a number L of bits, to a compressed output data binary string, having a number X of bits, characterized in that at least one sub-string anxe2x88x921anxe2x88x922 . . . a1a0 (1, 46, 70), having a number n of bits, of the input binary string is construed by assigning a integer numeric value N equal to the sum of the items of a monotonic increasing succession S={s0,s1,s2 , . . . } of integer numbers, among the first n items of such succession S, whose corresponding ai is equal to xe2x80x9c1,xe2x80x9d according to formula   N  =                              a                      n            -            1                          ·                  s                      n            -            1                              +                        a                      n            -            2                          ·                  s                      n            -            2                              +      …      +                        a          1                ·                  s          1                    +                        a          0                ·                  s          0                      =                  ∑                  i          =          0                          n          -          1                    ⁢              xe2x80x83            ⁢                        a          i                ·                  s          i                    
and, for each substring anxe2x88x921anxe2x88x922 . . . a1a0, a compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0 is created, comprising m bits, in which the binary representation of said integer numeric value N, as assigned to the corresponding sub-string anxe2x88x921anxe2x88x922 . . . a1a0, is stored, the binary representation of N being furnished by formula       N    =                                        d                          m              -              1                                ·                      2                          m              -              1                                      +                              d                          m              -              2                                ·                      2                          m              -              2                                      +        …        +                              d            1                    ·                      2            1                          +                              d            0                    ·                      2            0                              =                        ∑                      i            =            0                                m            -            1                          ⁢                  xe2x80x83                ⁢                              d            i                    ·                      2            i                                ,
said output data binary string comprising, for each sub-string anxe2x88x921anxe2x88x922 . . . a1a0, the corresponding compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0 and the data of said input binary string lacking of said at least one sub-string an anxe2x88x921anxe2x88x922 . . . a1a0, the ratio             R      k        =                  s        k                    s                  k          -          1                      ,
where k=1, 2, . . . , between two consecutive items of said succession S, fulfilling the condition expressed by formula
Rk less than 2 where kxe2x89xa7qxe2x89xa71,
the number n of bits of said at least one sub-string anxe2x88x921anxe2x88x922 . . . a1a0 being in the range between a minimum value nmin and the number L of bits included in said input data binary string, according to formula:
nminxe2x89xa6nxe2x89xa6L
the minimum value nmin being equal to the minimum value of n that fulfills the following condition:   m  =                    int        sup            ⁡              [                              log            2                    ⁡                      (                                          ∑                                  i                  =                  0                                                  n                  -                  1                                            ⁢                              xe2x80x83                            ⁢                              s                i                                      )                          ]               less than     n  
where the function y=intsup[x] returns the minimum integer value not lower than x (yxe2x89xa7x).
In particular, according to the invention, the first item s0 of said succession S is equal to 1 (s0=1), while the second item s1 of said succession S is equal to 2 (s1=2).
Again according to this invention, the ratio Rk between two consecutive items of said succession S trends to a constant value R when said index k increases, according to formula             lim              k        →        ∞              ⁢          R      k        =  R
Further according to this invention, said ratio Rk between two consecutive items of said succession S is never higher than 2, or
Rkxe2x89xa62 where kxe2x89xa71.
Again according to this invention, starting from the (r+1)-th item, or, for kxe2x89xa7r, each item sk of said succession S is equal to a polynomial of the p preceding items, where 1xe2x89xa6pxe2x89xa6r, according to formula             s      k        =                            ∑                      h            =            1                    p                ⁢                                            e              h                        ·                          s                              k                -                h                                              ⁢                      xe2x80x83                    ⁢          per          ⁢                      xe2x80x83                    ⁢          k                    ≥      r      ≥      p        ,
where the p coefficients eh, where h=1, 2, . . . , p, are constant positive, negative or zero integer numeric values.
In particular, the succession S is defined by the following formula:   S  =            S      Fib        =                  {                              s            0                    ,                      s            1                    ,                      s            2                    ,          …                }            =              {                                                                                                                        s                      0                                        =                    1                                                                                                                                          s                      1                                        =                    2                                                                                                                                                                  s                        k                                            =                                                                        s                                                      k                            -                            1                                                                          +                                                  s                                                      k                            -                            2                                                                                                                ⁢                                          xe2x80x83                                                                                            ⁢            where            ⁢                          xe2x80x83                        ⁢            k                    ≥          2                    
Preferably, according to this invention, nxe2x89xa710 or nxe2x89xa713.
The method according to this invention can comprise:
an initial step in which the information relating to the number L of bits of said input data binary string is stored;
a subsequent step in which the input binary string is assigned to an auxiliary string designated as xe2x80x9cCURRENT STRINGxe2x80x9d;
a loop of steps comprising in this order:
a compression block to compress the CURRENT STRING to a second auxiliary string designated as xe2x80x9cCOMPRESSED STRINGxe2x80x9d;
a check step to check whether said CURRENT STRING has been effectively compressed;
a check step, performed when the result of the preceding check step (7) is positive, to check whether said COMPRESSED STRING has a size greater than a pre-established value D, where D less than L,
an assignment step, performed when the result of the preceding check step is positive, to assign COMPRESSED STRING to CURRENT STRING, and subsequent repetition of the step loop, starting from said compression block;
a check step, performed when the result of one of the two preceding check steps is negative, to check whether the size of the juxtaposition of the information concerning the size L and of the COMPRESSED STRING is smaller than L;
an assignment step, performed when the result of the preceding check step that checks the size of the juxtaposition is positive, to assign the juxtaposition of the information relating to size L and of the COMPRESSED STRING to the output data binary string; and
an assignment step, performed when the result of the preceding check step that checks the size of the juxtaposition is negative, to assign the input data binary string to the compressed output data binary string.
In particular, the information concerning the number L of bits of the input data binary string is stored by a preestablished number t of bits.
According to a first embodiment of this invention, said step block for compressing said CURRENT STRING to said COMPRESSED STRING comprises the following steps:
subdividing said CURRENT STRING into l sub-strings comprising n bits, where nxe2x89xa7nmin, and
scanning said sub-strings at least once.
Preferably, according to this invention, said step block for compressing said CURRENT STRING to said COMPRESSED STRING, when the size W of said CURRENT STRING is not a multiple of n, fills at least a sub-string with a tail of bits equal to xe2x80x9c0.xe2x80x9d
Furthermore, said step block for compressing said CURRENT STRING to said COMPRESSED STRING, when the size W of said CURRENT STRING is not a multiple of n, fills the last sub-string with a tail of bits equal to xe2x80x9c0.xe2x80x9d
Again according to this invention, said block for compressing said CURRENT STRING to said COMPRESSED STRING, for each sub-string not comprising two consecutive bits equal to xe2x80x9c1,xe2x80x9d designated as canonical sub-string, and not successive to an other canonical sub-string, in the scanning order, creates a corresponding compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0.
Additionally, said block for compressing said CURRENT STRING to said COMPRESSED STRING, for each sub-string not comprising two consecutive bits equal to xe2x80x9c1,xe2x80x9d designated as canonical substring, creates a corresponding compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0.
In particular, said block for compressing said CURRENT STRING to said COMPRESSED STRUNG, performs a processing operation on each sub-string comprising at least two consecutive bits equal to xe2x80x9c1,xe2x80x9d designated as redundant or not canonical sub-string, and not successive in the scanning order to an other sub-string for which a compressed binary sub-string has been created, and, when the sub-string obtained by processing said redundant sub-string is canonical, creates a compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0 corresponding to said processed sub-string.
Additionally, said block for compressing said CURRENT STRING to said COMPRESSED STRING, performs a processing operation on each sub-string comprising at least two consecutive bits equal to xe2x80x9c1,xe2x80x9d designated as redundant or not canonical sub-string, and, when the sub-string obtained by processing said redundant sub-string is canonical, creates a compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0 corresponding to said processed sub-string.
Furthermore, said block for compressing said CURRENT STRING to said COMPRESSED STRING performs said processing operation during the same scan of the l sub-strings in which it creates the compressed binary sub-strings corresponding to the canonical sub-strings.
Again according to this invention, said block for compressing said CURRENT STRING to said COMPRESSED STRING performs said processing operation in a scan of the l sub-strings subsequent to the scan during which it creates the compressed binary sub-strings corresponding to the canonical sub-strings.
Again according to this invention, said compression block performs said processing operation for each redundant or not canonical sub-string that is not adjacent, in the scanning order, to another sub-string for which a compressed binary sub-string has been created.
In particular, said processing operation can include a logic NOT operation.
Furthermore, said processing operation can include a logic XOR operation with at least one mask or a logic XOR operation with a mask, comprising a number r of bits not higher than n (rxe2x89xa6n), which mask is defined as the one that makes the maximum number of redundant sub-strings to be processed canonical.
Again particularly, said processing operation can comprise a binary arithmetic operation, preferably performed by means of at least a binary constant, comprising a number r of bits not higher than n (rxe2x89xa6n).
Again according to this invention, said block for compressing said CURRENT STRING to said COMPRESSED STRING also creates a header string comprising, for each of the l sub-strings into which said CURRENT STRING is subdivided, an assembly of bits which indicates whether the corresponding sub-string of the CURRENT STRING has been compressed and/or whether the corresponding sub-string of the CURRENT STRING has been compressed after having been processed and/or the processing type performed on the corresponding sub-string of the CURRENT STRING.
In particular, the header string comprises l bits, each of which uniquely corresponds to a sub-string of the CURRENT STRING and it is equal to xe2x80x9c1,xe2x80x9d if the corresponding sub-string is compressed, or it is equal to xe2x80x9c0,xe2x80x9d if the corresponding sub-string is not compressed.
Further according to this invention, the header string comprises, for each sub-string of said CURRENT STRING that is compressed after having been processed, at least a corresponding bit to indicate the processing type performed on the corresponding sub-string.
In a particular embodiment of the method according to this invention, the header string further comprises said at least one mask.
In an other particular embodiment of the method according to this invention, the header string further comprises said at least one binary constant.
In particular, the block for compressing said CURRENT STRING to said COMPRESSED STRING also compresses said header string.
Still more particularly, said compression step block compresses at least one sub-string anxe2x80x2xe2x88x921anxe2x80x2xe2x88x922 . . . a1a0, having a number nxe2x80x2 of bits, where nxe2x80x2xe2x89xa6l, of the header string according to the method, in which the succession S is defined by the following formula:   S  =            S      Fib        =                  {                              s            0                    ,                      s            1                    ,                      s            2                    ,          …                }            =              {                                                                                                                        s                      0                                        =                    1                                                                                                                                          s                      1                                        =                    2                                                                                                                                                                  s                        k                                            =                                                                        s                                                      k                            -                            1                                                                          +                                                  s                                                      k                            -                            2                                                                                                                ⁢                                          xe2x80x83                                                                                            ⁢            where            ⁢                          xe2x80x83                        ⁢            k                    ≥          2                    
and particularly with nxe2x80x2=n.
Again according to this invention, said compression block compresses at least one sub-string anxe2x80x2xe2x88x921anxe2x80x2xe2x88x922 . . . a1a0, having a number nxe2x80x2 of bits, where nxe2x80x2xe2x89xa6l, of the header string according to the Run Length Encoding (RLE) method.
Further according to this invention, a flag comprising one or more bits is inserted ahead of or following to said COMPRESSED STRING, whose binary value indicates the compression type of the header string.
In a further embodiment of the method according to this invention, the block for compressing said CURRENT STRING to a COMPRESSED STRING comprises:
a first step iteration, in which a scan of the l sub-strings into which the CURRENT STRING is subdivided is effected and during which, for each sub-string not comprising two consecutive bits equal to xe2x80x9c1,xe2x80x9d designated as canonical sub-string, a corresponding compressed binary string dmxe2x88x921dmxe2x88x922 . . . d1d0 is created, a first header string being also created during such scan and comprising, for each of said l sub-string into which said CURRENT STRING is subdivided, a bit that is equal to xe2x80x9c1,xe2x80x9d if the corresponding sub-string is compressed, or a bit that is equal to xe2x80x9c0,xe2x80x9d if the corresponding sub-string is not compressed, and
one or more further step iterations, in which a processing operation is performed on each sub-string in respect of which, during the preceding iteration, no corresponding compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0 has been created, and, when the sub-string as furnished by said processing operation is canonical, a compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0 corresponding to the processed sub-string, is created; during each further iteration, a corresponding header string is created which comprises, for each sub-string in connection with which no corresponding compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0 has been created, a bit that is equal to xe2x80x9c1,xe2x80x9d if the corresponding sub-string has been compressed after having been processed, or a bit that is equal to xe2x80x9c0,xe2x80x9d if the corresponding sub-string is not compressed after having been processed.
In particular, said processing operation comprises a logic NOT and/or a logic XOR with at least one mask and/or a logic XOR with at least one mask including a number r of bits not higher than n (rxe2x89xa6n), which is designated as the mask that makes the maximum number of sub-strings, in respect of which no corresponding compressed binary sub-string dmxe2x88x921dmxe2x88x922 . . . d1d0 was created during the preceding iteration, canonical.
Further according to this invention, said header string further comprises said at least one mask.
Again according to this invention, that said processing operation comprises a binary arithmetic operation, particularly performed with at least one binary constant comprising a number r of bits not higher than n (rxe2x89xa6n).
Furthermore, said header string can comprise said at least one binary constant.
Again according to this invention, said step block for compressing said CURRENT STRING to said COMPRESSED STRING also compresses the first header string and/or at least one of said further header strings.
In particular, said compression block compresses the first header string and/or at least one of said further header strings according to the method in which said compression block compresses at least one sub-string anxe2x80x2xe2x88x921anxe2x80x2xe2x88x922 . . . a1a0, having a number nxe2x80x2 of bits, where nxe2x80x2xe2x89xa6l, of the header string according to the method, in which the succession S is defined by the following formula:   S  =            S      Fib        =                  {                              s            0                    ,                      s            1                    ,                      s            2                    ,          …                }            =              {                                                                                                                        s                      0                                        =                    1                                                                                                                                          s                      1                                        =                    2                                                                                                                                                                  s                        k                                            =                                                                        s                                                      k                            -                            1                                                                          +                                                  s                                                      k                            -                            2                                                                                                                ⁢                                          xe2x80x83                                                                                            ⁢            where            ⁢                          xe2x80x83                        ⁢            k                    ≥          2                    
and particularly with nxe2x80x2=n.
In further embodiment according to this invention, said block for compressing said CURRENT STRING to said COMPRESSED STRING comprises:
a) a first iteration of steps, in which:
a first scan of the CURRENT STRING is performed by means of a first window (59) having a size n11xe2x89xa6nmin not higher than a maximum value WD, said first window scanning said CURRENT STRING by shifting itself by a bit pitch WS1, in the range of 1 to WD (1xe2x89xa6WS1xe2x89xa6WD),
each time said first window identifies a sub-string not comprising two consecutive bits equal to xe2x80x9c1,xe2x80x9d designated as canonical sub-string Cn11 having a size n11, an index that identifies the position of said canonical sub-string Cn11 within said CURRENT STRING is stored and said canonical sub-string Cn11 is compressed to a compressed binary sub-string according to the Fibonacci compression procedure,
at the end of the scan, the number G1 of canonical sub-strings Cn11 that have been compressed and those portions of the CURRENT STRING not belonging to canonical sub-strings Cn11 having a size n11, are juxtaposed to one another in a first reject is string, and
b) one or more further steps in which
a scan of the reject string furnished by the preceding iteration is performed by means of a corresponding further window having a progressively decreasing size n1g less than n1gxe2x88x921, said further window scanning the concerned reject string by shifting itself by a bit pitch WSg in the range of 1 to WSgxe2x88x921 (1xe2x89xa6WSgxe2x89xa6WSgxe2x88x921),
each time said first windows identifies a canonical sub-string Cng having a size n1g, an index that identifies the position of said canonical sub-string Cng within said reject string furnished by said preceding iteration is stored and said canonical sub-string Cng is compressed to a compressed binary sub-string according to the Fibonacci procedure,
at the end of the scan, the number Gg of canonical sub-strings Cng that have been compressed and those portions of the reject string furnished by the preceding iteration, not belonging to canonical sub-strings Cng having a size n1g, are juxtaposed to one another in a corresponding further reject string,
the iteration of the steps being terminated when
the latest generated reject string is void, or
the latest generated reject string is too small to be effectively compressed, or
the size n1g of the last scanning window is equal to (nminxe2x88x921), said COMPRESSED STRING comprising:
the number F of scans performed up to the latest scan during which an effective compression operation has been performed,
the reject string generated by the latest iteration F, and
for each scan g, where g=1, . . . , F:
the number Gg of canonical sub-strings Cn1g that have been compressed,
for each canonical sub-string Cn1g:
the index igs (where s=1, . . . , Gg) identifying the position of the canonical sub-string within the reject string generated by the preceding iteration (gxe2x88x921), and
the compressed sub-string SCgs (where s=1, . . . , Gg).
In particular, said CURRENT STRING has a size not greater than a maximum value M and preferably M=1024.
Again according to this invention, WD less than M and preferably WD=64.
Again according to this invention, n1g =n1g xe2x88x921xe2x88x921.
Further according to this invention, WSg=WSgxe2x88x921.
In particular, according to this invention, WS1=1.
Preferably according to this invention, said block for compressing said CURRENT STRING to said COMPRESSED STRING comprises, preliminary to said first iteration of steps, a processing operation of said CURRENT STRING.
In a further embodiment of the method according to this invention, said block for compressing said CURRENT STRING to said COMPRESSED STRING comprises a first step for counting the number P of bits equal to xe2x80x9c1xe2x80x9d occurring in said CURRENT STRING.
In particular, when said number P fulfils the following condition             P      L         less than           (              1        -                  m          n                    )        ,
an extended string is created starting from the CURRENT STRING by juxtaposing a bit xe2x80x9c0xe2x80x9d to each of said P bits equal to xe2x80x9c1xe2x80x9d.
Further according to this invention, when said number P fulfils the following condition             P      L        ≥          (              1        -                  m          n                    )        ,
a logic NOT operation is performed on said current string and an extended string is created starting from the string generated by said not operation by juxtaposing a bit xe2x80x9c0xe2x80x9d to each bit equal to xe2x80x9c1xe2x80x9d.
In a further embodiment of the method according to this invention, said block for compressing said CURRENT STRING to said COMPRESSED STRING comprises performing a logic XOR operation on said CURRENT STRING by means of at least one mask comprising a number r of bits not higher than L (rxe2x89xa6L), designed in order that the string generated by said XOR operation fulfils the following condition             P      L         less than           (              1        -                  m          n                    )        ,
and subsequently creating an extended string starting from the string generated by said XOR operation by juxtaposing a bit xe2x80x9c0xe2x80x9d to each bit equal to xe2x80x9c1.xe2x80x9d
In a further embodiment of the method according to this invention, in the frame of said block for compressing said CURRENT STRING to said COMPRESSED STRING, each of said l sub-strings, into which said CURRENT STRING is subdivided is compressed to a compressed sub-string including a first portion, designated as xe2x80x9cmantissa,xe2x80x9d comprising a number m of bits, furnished by the method according to the Fibonacci compression procedure, and a second portion, designated as xe2x80x9cexponent,xe2x80x9d comprising a number z of bits, that is variable as the mantissa varies, where zxe2x89xa70 and equal to the number of bits needed for representing the number of n-bit strings to which the same integer numeric value N corresponds, when they are construed by means of the succession according to the Fibonacci compression procedure, said compression block further providing for pre-establishing an order of all of the n-bit strings, to which the same integer numeric value N corresponds, and for the exponent to identify the index of the redundant representation corresponding to the compressed sub-string, said COMPRESSED STRING comprising said compressed sub-strings.
In particular, according to this invention, when the number of n-bit strings to which the same integer numeric value N corresponds, when they are construed by means of the succession according to the Fibonacci compression procedure, is higher than 1, the string not comprising two consecutive bits equal to xe2x80x9c1,xe2x80x9d designated as canonical string, is expressed by said exponent by means of z bits equal to xe2x80x9c0.xe2x80x9d
Again according to this invention, said block for compressing said CURRENT STRING to said COMPRESSED STRING can comprise the following steps:
providing a redundancy ordering of all of said n-bit strings to which the same integer numeric value N corresponds, when they are construed by means of the succession according to Fibonacci, said string redundancy ordering including a first and a second redundancy order,
performing a first step iteration comprising:
compressing all of the sub-strings corresponding to the first redundancy order and storing information concerning their position within the input binary string
forming a first reject string by juxtaposing those portions of said input binary string not comprising sub-strings corresponding to the first redundancy order to one another,
performing a set of further step iterations, each in respect of a corresponding further redundancy order, each further iteration comprising:
compressing all of the sub-strings corresponding to the further redundancy order and storing information concerning their position within the reject string furnished by the preceding iteration,
forming a further reject string by juxtaposing those portions of said reject string furnished by said preceding iteration not comprising sub-strings corresponding to the further redundancy order to one another,
forming said COMPRESSED STRING by juxtaposing at least the following data for each iteration:
the number of compressed sub-strings,
the compressed sub-strings, and for each iteration with exclusion of the last one:
information concerning the positions of the compressed sub-strings within said input binary string or within said reject string furnished by said preceding iteration.
In particular, the method can be terminated as soon as all of the sub-strings into which the input binary string was subdivided are compressed.
Preferably, according to this invention, the n-bit strings construed according the Fibonacci succession, not comprising two consecutive bits equal to xe2x80x9c1xe2x80x9d and designated as canonical strings, belong to the first redundancy order.
This invention further concerns a method for decompression of a compressed binary string characterized in that said compressed binary string is generated starting from a data binary string comprising a number L of bits, by means of the described compression method.
This invention also covers an electronic apparatus comprising at least a central processing unit and at least a memory unit, characterized in that it performs the compression method as above described, as well as an electronic apparatus comprising at least a central processing unit and at least a memory unit, characterized in that it performs the described decompression method.
It is further subject matter of this invention an electric, magnetic or electromagnetic signal modulated by a digital signal comprising at least one data string, wherein said at least one data string is a compressed binary string generated, starting from a data binary string having a number L of bits, by means of the above compression method.
This invention further describes and claims a memory medium readable by a processor containing at least one data string, characterized in that said at least one data string is a compressed binary string generated, starting from a data binary string having a number L of bits, by means of the above described compression method.
Further specific subject matter of this invention is a processor program comprising code means adapted to perform, when they operate on a processor, the herein described and claimed compression method, as well as a memory medium readable by a processor, having a program stored therein, characterized in that said program is a processor program as above mentioned.
Again specific subject matter of this invention is a processor program comprising code means adapted to perform, when they operate on a processor, the herein described and claimed decompression method, as well as a memory medium readable by a processor, having a program stored therein, characterized in that said program is a processor program as above described.